module(..., package.seeall)

local LRUCache = {}
local LRUCache_mt = {__metatable = {}, __index = LRUCache}

function new(maxsize, max_age)
	local lru_cache = {
		-- Number of current cache entries
		current_items = 0,
		-- Number of maximum cache entries
		maxsize = maxsize,
		-- Number of seconds how long a cache entry should be valid
		max_age = max_age,
		head = {key = "head", next_ = nil, prev_ = nil},
		tail = {key = "tail", next_ = nil, prev_ = nil},
		-- Stores the cache entries
		data = {}
	}
	-- head/tail are nodes in the linked list, which are never be dropped.
	-- They are sentinels which make the operations on the linked list easier
	lru_cache.head.prev_ = lru_cache.tail
	lru_cache.tail.next_ = lru_cache.head
	setmetatable(lru_cache,LRUCache_mt)
	return lru_cache
end

function LRUCache.tostring(cache)
	local s=string.format("TYPE:LRU,MAX:%d,AGE:%d,CUR:%d",cache.maxsize,cache.max_age,cache.current_items)
	if cache.current_items>0 then
		s=s..'\n'
		local cur = cache.tail
		while cur ~= nil do
			s=s..'['..cur.key..']'
			cur = cur.next_
		end
		s=s..'\n'
	end
	return s
end

function LRUCache._add_entry(cache, entry)
	cache.head.prev_.next_ = entry
	entry.prev_ = cache.head.prev_

	cache.head.prev_ = entry
	entry.next_ = cache.head

	cache.current_items = cache.current_items + 1
	cache.data[entry.key] = entry
end

function LRUCache._remove_entry(cache, entry)
	cache.current_items = cache.current_items - 1
	cache.data[entry.key] = nil

	entry.prev_.next_ = entry.next_
	entry.next_.prev_ = entry.prev_
end

function LRUCache.del_last_entry(cache)
	if cache.current_items ~= 0 then
		cache:_remove_entry(cache.tail.next_)
	end
end

function LRUCache.set(cache, key, value)
	local entry = {
		-- If '_del_last_entry' is called the key is needed to remove
		-- the entry from cache.data
		key = key,
		value = value,
		max_age = os.time() + cache.max_age,
		next_ = nil,
		prev_ = nil
	}
	if cache.current_items > cache.maxsize then
		cache:_del_last_entry()
	end
	cache:_add_entry(entry)
end

function LRUCache.get(cache, key)
	local entry = cache.data[key]

	if entry == nil then
		return nil
	elseif entry.max_age > os.time() then
		-- Entry is there + young enough => Cache hit
		return entry.value
	else
		-- auto delete the entry because its too old to be kept
		cache:_remove_entry(entry)
		return nil
	end
end

function LRUCache.get_and_readd(cache, key)
	local entry = cache.data[key]

	if entry == nil then
		return nil
	elseif entry.max_age > os.time() then
		-- Entry is there + young enough => Cache hit
		entry.prev_.next_ = entry.next_
		entry.next_.prev_ = entry.prev_
		
		cache.head.prev_.next_ = entry
		entry.prev_ = cache.head.prev_

		cache.head.prev_ = entry
		entry.next_ = cache.head
		
		return entry.value
	else
		-- auto delete the entry because its too old to be kept
		cache:_remove_entry(entry)
		return nil
	end
end
